package com.leetcode.algorithm.y19.m01;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

import com.leetcode.algorithm.common.TreeNode;

/**
 * leetcode-cn.com
 * (done)94. 二叉树的中序遍历
 * (done)144. 二叉树的前序遍历
 * (TODO)145. 二叉树的后序遍历
 * 
 * @author: jie.deng
 * @time: 2019年1月19日 下午4:29:09
 */
public class MySolution0120Stack {
	
    /**
     * 94. 二叉树的中序遍历
     * 
     * 给定一个二叉树，返回它的中序 遍历。
     * 
     * 示例:
     * 
     * 输入: [1,null,2,3]
     *    1
     *     \
     *      2
     *     /
     *    3
     * 
     * 输出: [1,3,2]
     * 进阶: 递归算法很简单，你可以通过迭代算法完成吗？
     * @param root
     * @return
     */
	public List<Integer> inorderTraversal(TreeNode root) {
		List<Integer> list = new ArrayList<Integer>();
		if (root == null) {
			return list;
		}
		
		Stack<TreeNode> stack = new Stack<TreeNode>();
		TreeNode cur = root;
		boolean popFlag = false;
		while (cur != null) {
			if (cur.left != null && !popFlag) {
				stack.push(cur);
				printStack(stack);
				cur = cur.left;
			} else {
				list.add(cur.val);
				if (cur.right != null) {
					cur = cur.right;
					popFlag = false;
				} else {
					if (stack.isEmpty()) {
						break;
					}
					cur = stack.pop();
					printStack(stack);
					popFlag = true;
				}
			}
		}
		return list;
	}

	public List<Integer> inorderTraversal2(TreeNode root) {
		List<Integer> list = new ArrayList<Integer>();
		if (root == null) {
			return list;
		}
		Stack<TreeNode> stack = new Stack<TreeNode>();
		TreeNode cur = root;
		while (cur != null || !stack.isEmpty()) {
			while (cur != null) {
				stack.push(cur);
				printStack(stack);
				cur = cur.left;
			}
			if (!stack.isEmpty()) {
				cur = stack.pop();
				printStack(stack);
				list.add(cur.val);
				cur = cur.right;
			}
		}
		return list;
	}
    
	/**
     * 144. 二叉树的前序遍历
     * 
     * 给定一个二叉树，返回它的 前序 遍历。
     * 
     *  示例:
     * 
     * 输入: [1,null,2,3]  
     *    1
     *     \
     *      2
     *     /
     *    3 
     * 
     * 输出: [1,2,3]
     * 进阶: 递归算法很简单，你可以通过迭代算法完成吗？
     * @param root
     * @return
     */
	public List<Integer> preorderTraversal(TreeNode root) {
		List<Integer> list = new ArrayList<Integer>();
		if (root == null) {
			return list;
		}
		Stack<TreeNode> stack = new Stack<TreeNode>();
		TreeNode cur = root;
		while (cur != null) {
			list.add(cur.val); // 先序遍历
			if (cur.left == null && cur.right == null) {
				// 叶子节点
				if (stack.isEmpty()) {
					break;
				}
				cur = stack.pop();
				printStack(stack);
				cur = cur.right;
			} else if (cur.left != null && cur.right != null) {
				// 同时有左子树+右子树
				stack.push(cur); // 入栈，遍历完左子树之后，出栈遍历右子树
				printStack(stack);
				cur = cur.left;
			} else {
				// 只有左子树或者右子树
				cur = cur.left == null ? cur.right : cur.left;
			}
		}
		return list;
	}	
	public List<Integer> preorderTraversal2(TreeNode root) {
		List<Integer> list = new ArrayList<Integer>();
		if (root == null) {
			return list;
		}
		Stack<TreeNode> stack = new Stack<TreeNode>();
		TreeNode cur = root;
		while (cur != null || !stack.isEmpty()) {
			while (cur != null) {
				list.add(cur.val);
				stack.push(cur);
				printStack(stack);
				cur = cur.left;
			}
			if (!stack.isEmpty()) {
				cur = stack.pop();
				printStack(stack);
				cur = cur.right;
			}
		}
		return list;
	}
	
	private void printStack(Stack<TreeNode> stack) {
		List<TreeNode> list = new ArrayList<TreeNode>(stack);
		StringBuffer sbStr = new StringBuffer();
		for (TreeNode treeNode : list) {
			sbStr.append((char) treeNode.val);
		}
		System.out.println(sbStr.toString());
	}



	/**
     * 145. 二叉树的后序遍历
     * 
     * 给定一个二叉树，返回它的 后序 遍历。
     * 
     * 示例:
     * 
     * 输入: [1,null,2,3]  
     *    1
     *     \
     *      2
     *     /
     *    3 
     * 
     * 输出: [3,2,1]
     * 进阶: 递归算法很简单，你可以通过迭代算法完成吗？
     * @param root
     * @return
     */
	public List<Integer> postorderTraversal(TreeNode root) {
		return null;
	}


}
